Kadane's Algorithm

AI Generated

Kadane’s Algorithm is a dynamic programming technique used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers — both positive and negative.

---

Problem Statement

Given an array arr[], find the maximum sum that can be obtained from a contiguous subarray.

---

Algorithm Steps

1. Initialize:

   • max_current = arr[0]
   • max_global = arr[0]

2. Traverse the array from index 1 to end:

   • At each step: max_current = max(arr[i], max_current + arr[i]) This decides whether to:

     • Start a new subarray at arr[i]
     • Or extend the previous subarray

   • Update global max: max_global = max(max_global, max_current)

3. Return max_global — the largest sum found.

---

Python Implementation

def kadane(arr):
    max_current = max_global = arr[0]

    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        max_global = max(max_global, max_current)

    return max_global

---

Example

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Output: 6 (from subarray [4, -1, 2, 1])

---

Time and Space Complexity

• Time: O(n)
• Space: O(1)

---

✅ Key Use Case

Kadane's Algorithm is widely used in problems involving:

• Maximum subarray sums
• Financial data (e.g. maximum profit)
• Image and signal processing